Miller-Rabin randomized primality test (1976, 1980)

There is a randomized algorithm running in $O(n^3 \log_2(1/\delta))$ time that, with probability $1-\delta$ determines if an $n$ -bit integer $x$ is prime.

MillerRabin(n) If $n > 2$ and $n$ is even, return composite. /* Factor $n − 1$ as $2^s t$ where $t$ is odd. */ $s ← 0$ $t ← n − 1$ while $t$ is even $s ← s + 1$ $t ← t/2$ end /* Done. $n − 1 = 2^s t$ . */ Choose $x ∈ \{1, 2, . . . , n − 1\}$ uniformly at random. Compute each of the numbers $x_t , x^{2t} , x^{4t} , . . . , x^{2^st} = x^{n−1} \mod n$ . If $x^{n−1} \not\equiv 1 \pmod n$ , return composite. for $i = 1, 2, . . . , s$ If $x^{2^i t} ≡ 1 \pmod n$ and $x^{2^{i−1} t} \not\equiv ±1 \pmod n$ , return composite. end /* Done checking for fake square roots. */ Return probably prime.